초경량 FTL을 위해서 깔짝거리던 노트 일단 복원해 둠.
요 며칠 새로운 아이디어를 넣어서 비벼봤는데 잘 안 되고 있다. 상용 SSD 같은 건 좋은 알고리즘이 이미 들어가있겠지만.
중간 정리.
이 놈의 FTL은 공간지각력이 딸리면 그림이 안 그려진다.
블럭 사용 빈도에 대한 확률 분포를 고려해서, 통계를 뽑고 대안 알고리즘을 모색해 볼 수도 있다.
주로 블럭머지와 가비지 컬렉션 방법과 빈도에 관한 문제가 될 것이다.
.
.
.
블럭 = 2048개
블럭당 페이지 = 64개
페이지당 섹터 = 4개
페이지 크기 : 2048바이트
스페어 크기 : 64바이트
삭제 크기 : 128KB
스페어는 알뜰하게 써보자면.
블럭 번호 = 2바이트 / unsigned short
페이지 오프셋 = 6비트
섹터 오프셋 = 2비트 // 얘네는 합쳐서 unsigned char 니까..
스페어를 비트필드 구조체로 잡고 캐스팅해서 쓰자.
---------------------------------------------------------------
* 한 섹터의 정보는 3바이트로 표시할 수 있다.
* 한 페이지에는 섹터 4개가 들어간다.
* 한 페이지에 섹터 정보를 모두 표시하려면 12바이트가 필요하다.
* 한 페이지의 스페어 크기는 64바이트므로 널널하다.
-------------------------------------------------------------------
* 각 섹터별 사용중 체크를 1바이트씩 하자.
* 이 사용중 체크를 섹터 정보 마지막 바이트로 0101010.. 0으로 끝나게 구성하면 더티 비트화 된다.
* 그렇다면 4*4 = 16바이트가 섹터 정보다.
* 여기서 쓰기 직전에 스페어에 기록을 하자 0x6A가 좋겠다.
* 그렇다면 5바이트씩 * 4 = 20 바이트가 섹터 정보다.
즉 [시작 더티][블럭 하이][블럭 로우][페이지 옵셋 | 섹터 옵셋 << 6][끝 더티]
끝 더티는 사용중 체크임
----------------------------------
1. 섹터 번호가 주어졌다.
--> 페이지까지 접근하자.
섹터 번호 / 4 = 페이지 번호
섹터 번호 % 4 = 섹터 오프셋
9 섹터의 경우 : 페이지 번호는 2, 섹터 오프셋은 1
----------------------------------
2. 페이지 번호와 섹터 오프셋으로 섹터 번호를 찾자.
페이지 번호 2, 섹터 오프셋 1인 경우 -> 2 * 4 + 1= 9
----------------------------------
3. 페이지 번호가 나왔다. 블럭 번호를 찾자.
페이지 번호 / 4 = 블럭 번호
페이지 번호 % 4 = 페이지 오프셋
----------------------------------
4. 12321 섹터의 위치를 찾아보자.
12321 / 4 = 3080 (페이지 번호), 나머지는 1 (섹터 오프셋)
3080 / 64 = 48 (블럭 번호), 나머지는 8 (페이지 오프셋)
----------------------------------
결과 :
48블럭, 8페이지, 1번째 섹터
------------------------------------------------------
작업 스테이지를 나눠보자.
----------------------------------
-1 풀 이레이징
다 지운다.
에러가 나도 무시하자. 배드면 어차피 0x00이 남는다.
여기서 부터 체킹 하면 귀찮다. 미리 테이블을 구성한다고 빠를 것이 없다.
-1.1 FTL 포맷팅
데이터시트에 나온데로 각 블럭의 1페이지, 2페이지 스페어의 첫 바이트만 읽어서 0xFF인가 확인한다.
배드가 아니면 1페이지 스페어 3, 4 위치에 논리 블럭 번호를 증가 시키면서 기록한다.
-1.2 클리어링
룩업테이블.물리블럭번호 = 0xFFFF로 전부 놓는다.
----------------------------------
-2 스캐닝
빵구 카운트 R = 0이다.
데이터시트에 나온데로 각 블럭의 1페이지, 2페이지 스페어의 첫 바이트만 읽어서 0xFF인가 확인한다.
1페이지 스페어 3, 4 위치에 논리 블럭 번호를 읽는다.
룩업테이블[읽은 논리블럭번호].물리블럭번호 = 3
1페이지 스페어 3, 4 위치에 읽은 논리 블럭 번호가 0xFFFF면 그 텀은 걍 스킵하고 빵구 카운트 R을 증가시킨다.
블럭 2000개 중에서 중간에 배드가 3개가 있다면 룩업테이블[1999].물리블럭번호 = 2002다.
예) 3번 블럭에서 읽은 논리 블럭 번호가 5면 LUT[5].pblock = 3
----------
-2 스캐닝 중 빵구 블럭 때우기
j = 0;
while(1) {
refind:
for (i = 0; i < 2048; i++) {
if (LUT[i].pblock == j) {
j++;
goto refind;
}
}
if (i == 2048) { // 못찾은 것이다.
for (i = 0; i < 2048; i++) {
if (LUT[i].pblock == 0xFFFF) {
LUT[i].pblock = j++;
break;
}
pblock 위치에 논리 블럭값 i를 쓴다.
}
}
}
룩업테이블을 한 바퀴 돌리면서 물리블럭번호가 0xFFFF가 아닌 것중 가장 작은 값을 찾는다.
----------------------------------
-3 최초 쓰기 (4 또 쓰기 루틴을 정상적으로 밟아야 함)
섹터 넘버로 쓰기 접근이 발생했다.
3.1 위 공식으로 위치를 찾는다.
3.2 섹터를 기록한다.
3.3 스페어의 해당 섹터 정보 위치에 "사용중" 체크를 한다. 0x6A가 적당하다. = 1101010B
----------------------------------
-4 또 쓰기 (5 또또 쓰기 루틴을 정상적으로 밟아야 함)
같은 위치에 쓰기 접근이 발생했다.
4.1 위 공식으로 위치를 찾는다.
4.2 해당 섹터 스페어 정보를 읽어서 사용중인가 본다.
4.3 사용중이 아니면 3번 코스다.
4.4 사용중이면 빈 섹터를 찾는다.
4.5 빈 섹터에 기록하고 빈 섹터 번호를 지금 위치 페이지의 스페어의 해당 섹터 정보 위치에 기록한다.
4.6 사용중 체크까지 한다.
----------------------------------
-5 또또 쓰기
아까 그 위치에 또 쓰기 접근이 발생했다.
5.1 위 공식으로 위치를 찾는다.
5.2 해당 섹터 스페어 정보를 읽어서 "사용중"이 표시되어 있는지 본다.
5.3 사용중이 아니면 3번 코스다.
5.4 사용중이면 읽은 스페어 섹터 정보를 보고 대치된 섹터 위치가 있는지 본다.
5.5 대치된 섹터가 있다면 해당 섹터로 점프
5.6 없다면 4번 코스다.
-----------------------------------
최초 부팅 스캐닝을 생각해보자.
아싸리 프리 블럭인 놈들은 구분해놓고 프리 섹터 풀로 사용해야 한다.
각 블럭 0페이지, 1페이지 스페어 0번째 바이트는 0xFF로 항상 내비둔다.
- 아니면 손쉽게 배드
********** 각 블럭 0페이지 1번째 바이트를 사용 블럭 표시자로 쓰자.
1번째 바이트가
-- 0xFF = 풀프리
-- 0x1A = 한 페이지라도 썼다능
-- 0x1A 인 경우
2번째 바이트가
-- 0xFF = 아직 남은 섹터가 있다능
-- 0X5B = 꽉꽉 채웠다능
자 일케 해 놓고 스캔할때는
1. 풀 스캔하면서
2. 룩업테이블[논리블럭번호].프리상태 = 풀프리냐 반프리냐 꽉꽉이냐 셋팅!!
-------------------
프리 섹터는 어떻게 찾는가?
섹터 단위로 프리 섹터를 찾는 건 무모하다.
* 전 섹터에 대한 맵핑을 구성하면 램을 오방 먹는다.
* 부팅때 맵핑 테이블 구축하기 위해서 전 스페어를 스캐닝해야 한다. -> 부팅 존나 느려짐
- 블럭단위로 꽉꽉 채워서 프리 섹터를 나눠주는 것이 낫다.
- 블럭단위로 꽉꽉 채워서 프리 섹터를 나눠 줄 수 없는 지경에 이르면 어떻게 하는가?
------>
* 루프 돌면서 룩업테이블[논리블럭번호].프리상태 = 풀프리면 그 프리 첫 섹터 반환예정
* 해당 블럭 0페이지 스페어 1번 바이트 반프리로 변경씀
* 룩업테이블[논리블럭번호].프리상태 = 반프리로 변경
* 프리 섹터 반환
--> 아니다 반프리로 변경하고 리턴한다.
-----> 파워 페일이 났을 경우 리턴했던 페이지는 쓰다만 페이지이므로 어차피 프리 페이지가 아니다.
-----> 한 바이트도 못 썼다 할지라도 프리 페이지가 아니다.
-------> 이 상황이 누적되면 용량 감소가 발생할 수 있으나 가비지 컬렉션에서 해결한다.
* 루프 돌면서 룩업테이블[논리블럭번호].프리상태 = 반프리면
* 해당 블럭의 스페어 순차적으로 점검하여 빈 섹터 찾아놓는다.
* 섹터 끝까지 다 썼으면 (64 *4) 이면,
* 룩업테이블[논리블럭번호].프리상태 = 꽉꽉으로 변경(꽉꽉 아니면 말구~)
* 해당 블럭 0페이지 스페어 2번 바이트 꽉꽉으로 변경 (꽉꽉 아니면 말구~)
* 빈섹터 리턴한다.
------------- 프리섹터 찾기 최장 시크 타임을 줄이려면
* 룩업테이블 마지막부터 프리블럭을 앞으로 스캔해온다.
* 마지막 프리블럭에서 꽉꽉으로 끝났으면 current_free_block--;
* 마지막 프리블럭에서 반프리로 끝났으면 걍 관둠.
-- current_free_block == 0 이면 마지막으로 도로 보냄.
----------
읽기작업은?
1. 섹터로 위치를 찾는다. 블럭, 페이지 옵셋, 섹터 옵셋.
2. 룩업테이블[논리블럭번호].물리블럭번호에서. 페이지 옵셋, 섹터 옵셋으로 간다.
3. 해당 스페어의 "끝 더티" 표시가 안 되어 있다면 버퍼 0으로 채워서 리턴 (페이지에 진짜 쓴 것이 없다)
4. 끝 더티가 있다면 한 번만 쓴 페이지므로 섹터 읽어서 리턴
5. 해당 스페어의 "시작 더티" 는 있는데 "끝 더티"가 이상하면 문제 있는 섹터다.
6. "시작 더티"가 있고 대치 페이지가 있다면 그 위치로 다시 찾아감 1로 시작
문제 있는 섹터 발견했다면 그 블럭에 대해서 가비지 컬렉션 통째로 수행
1. 블럭 통째로 읽음 -> 읽으면서 문제 있던 섹터는 다 지우고 프리 상태로 만듬
2. 풀프리 블럭을 찾음. = C
루프 돌면서 룩업테이블[논리블럭번호].프리상태 = 풀프리 찾음
2.5 풀프리 블럭의 논리블럭 번호를 읽음 = A
3. 풀프리 블럭 C를 지움.
4. 새로운 논리 블럭 번호를 씀 (원 블럭의 논리 블럭번호 B, 원블럭.물리블럭번호=D)
5. 블럭 버퍼를 순서대로 씀.
6. 스페어에 반프리 표시
7. 룩업테이블[B].프리상태 = 반프리 표시
7. 룩업테이블[B].물리블럭번호 = C
8. 원래 블럭 D를 지움 ( 이 사이에 파워 페일이 발생하면 스캔시 논리 블럭을 안 가진 빵구 블럭이 존재한다)
9. 원래 블럭 D에 A를 씀
10. 룩업테이블[A].프리상태 = 풀프리
11. 룩업테이블[A].물리블럭번호 = D
-------------
프리 블럭이 없을때..
파워 페일과 가비지 컬렉션은?
댓글.2 / 엮인글 / HanRSS 구독
엮인글 주소 :: 이 글에는 트랙백을 보낼 수 없습니다
dawnsea 2009/09/23 11:08 X O
--> 나이를 추가하자
즉 [시작 더티][블럭 하이][블럭 로우][페이지 옵셋 | 섹터 옵셋 << 6][나이][끝 더티]
쓸때마다 나이를 증가(혹은 FF에서 감소시킨다)
dawnsea 2009/09/23 11:23 X O
파워 페일과 가비지 컬렉션은?
반프리 + 풀프리 블럭이 정해 놓은 임계 수치 이하로 떨어지면
가비지 컬렉션으로 들어간다.
1. current_free_block을 증가시키는 방향으로 꽉꽉 블럭을 찾는다.
2. 꽉블럭에서 정한 임계 나이보다 어린 섹터를 찾는다.
3. 어린 섹터면 읽기 작업 참고하여 목적지 섹터까지 훑는다.
4. 빈 블럭 버퍼에 가지친 정보로 차곡차곡 정리한다.
5. 문제 있는 섹터 발견했을 때 하는 방식 처럼 블럭 체인지 한다.